/*
 * @lc app=leetcode.cn id=130 lang=golang
 *
 * [130] 被围绕的区域
 */

// @lc code=start
func solve(board [][]byte) {
	// 初始化行、列
	m = len(board)
	n = len(board[0])
	// 初始化需要修改的区域的点
	needchange = make([]*Node, 0, m+n)
	// 初始化队列
	queue = make([]*Node, 0)
	// 初始化访问列表
	visited = make([][]bool, m)

	for i, _ := range visited {
		visited[i] = make([]bool, n)
	}

	// 遍历
	for x := 0; x < m; x++ {
		for y := 0; y < n; y++ {
			// 当点未‘O’时，且未访问，初始化设置边缘标志，广度遍历点的上下左右
			if board[x][y] == 'O' && !visited[x][y] {
				isMargin = false
				bfs(board, x, y)
			}
		}
	}
	// 遍历需要修改的区域的点，将其修改
	for _, node := range needchange {
		board[node.x][node.y] = 'X'
	}
}

func bfs(board [][]byte, x, y int) {
	// 记录初始长度，方便还原
	length := len(needchange)
	newnode := &Node{x, y}
	// 入队，并设置已访问
	queue = append(queue, newnode)
	visited[x][y] = true
	for len(queue) > 0 {
		// 出队
		node := queue[0]
		queue = queue[1:]
		// 将要修改的点加入到列表

		// 当存在点在地图边缘时，设置边缘标志（此次遍历的点都不能修改）
		if node.x == 0 || node.y == 0 || node.x == m-1 || node.y == n-1 {
			isMargin = true
		}
		if !isMargin {
			needchange = append(needchange, node)
		}
		// 遍历点的上下左右
		for i := 0; i < 4; i++ {
			nx := node.x + dx[i]
			ny := node.y + dy[i]
			// 越界处理
			if nx < 0 || ny < 0 || nx >= m || ny >= n {
				continue
			}
			// 当点未‘O’时，且未访问，入队,并设置已访问
			if board[nx][ny] == 'O' && !visited[nx][ny] {
				queue = append(queue, &Node{nx, ny})
				visited[nx][ny] = true
			}
		}
	}
	// 当存在在地图边缘的点，本次遍历加入的点全部舍弃
	// 还原要修改的列表到初始的长度
	if isMargin {
		needchange = needchange[:length]
	}
}

// 行
var m int

// 列
var n int

// 保存需要修改的区域的列表
var needchange []*Node

// 队列（广度优先）
var queue []*Node

// 区域中是否包含在边缘的点
var isMargin bool

// 保存访问过的列表
var visited [][]bool

// 点的        上  下 左  右
var dx = []int{0, 0, -1, 1}
var dy = []int{1, -1, 0, 0}

// 保存下标的数据结构
type Node struct {
	x int
	y int
}

// @lc code=end

